package ljl.codetop;

import java.util.LinkedList;
import java.util.List;

public class _200_num_islands {

    /**
     * dfs bfs 都行，递归就是 dfs，非递归就是 bfs，你懂我意思吧
     *
     * 改了一千次才改对
     */
    static class trydfs {

        public int numIslands(char[][] grid) {
            int m = grid.length, n = grid[0].length;
            boolean[][] visited = new boolean[m][n];
            int res = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (visit(visited, grid, i, j)) {
                        res++;
                    }
                }
            }
            return res;
        }
        boolean visit(boolean[][] visited, char[][] grid, int i, int j) {
            if (i < 0 || j < 0 || i >= visited.length || j >= visited[0].length || visited[i][j] || grid[i][j] == '0') return false;
            visited[i][j] = true;
            boolean res = true;
            visit(visited, grid, i + 1, j);
            visit(visited, grid, i, j + 1);
            visit(visited, grid, i - 1, j);
            visit(visited, grid, i, j - 1);
            return res;
        }
    }

    /**
     * bfs 必然得有个队列
     *
     * todo 这个解法我也搞了很长时间，原因是：应该声明新变量，我却：x += 1，导致错了，debug 了半天
     */
    static class trybfs {

        public int numIslands(char[][] grid) {
            int m = grid.length, n = grid[0].length;
            int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            boolean[][] visited = new boolean[m][n];
            int res = 0;
            LinkedList<int[]> posList = new LinkedList<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (!visited[i][j] && grid[i][j] == '1') {
                        res++;
                        posList.offer(new int[] {i, j});
                        visited[i][j] = true;
                        while (!posList.isEmpty()) {
                            int[] pos = posList.poll();
                            int xx = pos[0], yy = pos[1];
                            for (int[] dir : dirs) {
                                int x = xx + dir[0];
                                int y = yy + dir[1];
                                if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y] && grid[x][y] == '1') {
                                    visited[x][y] = true;
                                    posList.offer(new int[] {x, y});
                                }
                            }
                        }
                    }
                }
            }
            return res;
        }
    }

    /**
     * 我不喜欢这个解法
     */
    static class off1 {
        void dfs(char[][] grid, int r, int c) {
            int nr = grid.length;
            int nc = grid[0].length;

            if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
                return;
            }

            grid[r][c] = '0';
            dfs(grid, r - 1, c);
            dfs(grid, r + 1, c);
            dfs(grid, r, c - 1);
            dfs(grid, r, c + 1);
        }

        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0) {
                return 0;
            }

            int nr = grid.length;
            int nc = grid[0].length;
            int num_islands = 0;
            for (int r = 0; r < nr; ++r) {
                for (int c = 0; c < nc; ++c) {
                    if (grid[r][c] == '1') {
                        ++num_islands;
                        dfs(grid, r, c);
                    }
                }
            }

            return num_islands;
        }
    }


    /**
     * 这个也很丑陋 令人生厌
     */
    static class off2 {
        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0) {
                return 0;
            }

            int nr = grid.length;
            int nc = grid[0].length;
            int num_islands = 0;

            for (int r = 0; r < nr; ++r) {
                for (int c = 0; c < nc; ++c) {
                    if (grid[r][c] == '1') {
                        ++num_islands;
                        grid[r][c] = '0';
                        LinkedList<Integer> neighbors = new LinkedList<>();
                        neighbors.add(r * nc + c);
                        while (!neighbors.isEmpty()) {
                            int id = neighbors.remove();
                            int row = id / nc;
                            int col = id % nc;
                            if (row - 1 >= 0 && grid[row-1][col] == '1') {
                                neighbors.add((row-1) * nc + col);
                                grid[row-1][col] = '0';
                            }
                            if (row + 1 < nr && grid[row+1][col] == '1') {
                                neighbors.add((row+1) * nc + col);
                                grid[row+1][col] = '0';
                            }
                            if (col - 1 >= 0 && grid[row][col-1] == '1') {
                                neighbors.add(row * nc + col-1);
                                grid[row][col-1] = '0';
                            }
                            if (col + 1 < nc && grid[row][col+1] == '1') {
                                neighbors.add(row * nc + col+1);
                                grid[row][col+1] = '0';
                            }
                        }
                    }
                }
            }
            return num_islands;
        }
    }

    static class lufei2 {
        public int numIslands(char[][] grid) {
            int count = 0;
            for(int i = 0; i < grid.length; i++) {
                for(int j = 0; j < grid[0].length; j++) {
                    if(grid[i][j] == '1'){
                        bfs(grid, i, j);
                        count++;
                    }
                }
            }
            return count;
        }
        private void bfs(char[][] grid, int i, int j){
            LinkedList<int[]> list = new LinkedList<>();
            list.add(new int[] { i, j });
            while(!list.isEmpty()){
                int[] cur = list.remove();
                i = cur[0]; j = cur[1];
                if(0 <= i && i < grid.length && 0 <= j && j < grid[0].length && grid[i][j] == '1') {
                    grid[i][j] = '0';
                    list.add(new int[] { i + 1, j });
                    list.add(new int[] { i - 1, j });
                    list.add(new int[] { i, j + 1 });
                    list.add(new int[] { i, j - 1 });
                }
            }
        }
    }

    /**
     * 这个也费了我得有二十分钟为啥呢
     * 因为有行代码写错了，很低级的错误
     */
    static class copy_lufei2 {

        public int numIslands(char[][] grid) {
            int m = grid.length, n = grid[0].length;
            boolean[][] visited = new boolean[m][n];
            int res = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (!visited[i][j] && grid[i][j] == '1') {
                        res++;
                        bfs(visited, grid, i, j);
                    }
                }
            }
            return res;
        }
        void bfs(boolean[][] visited, char[][] grid, int x, int y) {
            LinkedList<int[]> list = new LinkedList<>();
            list.offer(new int[] {x, y});
            while (!list.isEmpty()) {
                int[] pos = list.poll();
                int i = pos[0], j = pos[1];
                if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0' || visited[i][j]) continue;
                visited[i][j] = true;
                list.add(new int[] {i + 1, j});
                list.add(new int[] {i, j + 1});
                list.add(new int[] {i - 1, j});
                list.add(new int[] {i, j - 1});
            }
        }
    }
}
